Programmed logic arrays (PLAs) provide an easily designed and well structured alternative to combinatorial logic.
Internally, a conventional prior art PLA comprises two logic arrays known as the DECODER array and the ROM array. The two arrays are electrically connected by paths known as wordlines. Each wordline corresponds to one minterm of the Boolean functions implemented by the PLA. PLA input signals are entered into the DECODER array on a plurality of input lines and PLA output signals emanate from the ROM array on a plurality of output lines.
A PLA is in many ways similar to a Read-Only-Memory (ROM). As black boxes, both are presented with a binary input word and in response both output a predefined binary word. The most significant difference between a PLA and a ROM is that in the former every possible combination of binary input signals (of which there are 2.sup.N for N PLA input lines) is not presented. A typical PLA produces a meaningful output only in response to certain preselected combinations of binary input signals. These preselected combinations generally number less than 2.sup.N for a PLA having N inputs. If a given one of the preselected combinations of binary input signals is present on the PLA input lines, then a given preselected combination of binary output signals emanates from the PLA. If the combination of binary input signals present on the PLA input lines does not correspond to a given one of the preselected combinations of binary input signals, the PLA may not produce a meaningful output. In contrast, a ROM having N input lines will always produce a unique binary output for each of the 2.sup.N unique combinations of binary input signals. As a result, for the same technology of fabrication the PLA is generally smaller and faster than the ROM which would be required to replace it, assuming implementation of the same Boolean functions.
When specifying Boolean functions to be implemented in hardware, it is often the case that there are combinations of input signals that contain don't cares. That is, one or more of the input signals are not needed to uniquely determine the output. When designing with conventional combinatorial and sequential logic which includes gates and registers, there are many optimization techniques, such as Karnaugh mapping, that take advantage of these don't cares to reduce logic complexity. When replacing conventional combinatorial logic with ROM, there is no way to make use of this savings because a unique output pattern will exist for every one of the 2.sup.N combinations of input signals that can be entered into a ROM having N binary input lines. However, a PLA differs from a ROM in that don't cares are taken advantage of and a savings accrues. Preselected combinations of binary PLA input signals may be incompletely specified, or fully specified, as the designer sees fit.
To further understand the type of function which can be implemented with a conventional PLA, it is useful to consider an illustrative PLA which has four input lines, three output lines and two wordlines (corresonding to two Boolean minterms), and which implements the following Boolean function:
______________________________________ IF (input 1 = 1 AND input 2 = 0 AND input 3 = 1 AND input 4 = X) (X is a don't care which can be zero or one) THEN (output 1 = 1 output 2 = 1 output 3 = 0) OR IF (input 1 = 1 AND input 2 = X AND input 3 = 1 AND input 4 = 1) (X is a don't care which can be zero or one) THEN (output 1 = 1 output 2 = 0 output 3 = 0) ______________________________________
A conventional prior art PLA which implements this Boolean function is illustrated in FIG. 1. In the above-mentioned PLA example, if either of the preselected combinations of binary input signals is present on the PLA input lines, the corresponding combination of binary PLA output signals results. (Note, that in the above-mentioned PLA example, the use of don't cares indicates that the preselected combinations of binary input signals are incompletely specified.) If the combination of binary signals present on the PLA input lines does not correspond to either of the preselected combinations of binary input signals, no meaningful PLA output results.
Thus, as can be seen from the above-mentioned Boolean function, the conventional PLA should be viewed by the designer as implementing a series of IF, THEN statements. This can be understood by considering the internal operation of the PLA as shown in FIG. 1. This PLA has two wordlines connecting the ROM and DECODER arrays. There is one wordline corresponding to each incompletely specified preselected combination of input signals. There is no ELSE construct which can be used to produce a meaningful PLA output if neither of the two (101X and 1X11) preselected combination of PLA input signals is present on the PLA input lines.
Providing a true ELSE construct would allow one to design a PLA capable of implementing functions similar to the IF, THEN, or ELSE, i.e., CASE statements of a high-level computer language. A CASE statement is thus a series of IF, THENs followed by an ELSE. A PLA which implements a CASE statement should be able to produce a meaningful Boolean output to indicate that none of a plurality of preselected combinations of binary input signals is present on the PLA input lines. In other words, IF one of the plurality of preselected combinations of binary input signals is present on the PLA input lines, THEN the corresponding PLA output results, ELSE an output, indicating the simultaneous absence of all of the plurality of preselected combinations of binary input signals, results.
Availability of a PLA able to implement CASE statements would be especially useful in the design of microprogrammable microprocessor control structures. Accordingly, efforts have been directed to the development of a PLA adapted to implement IF, THEN, or ELSE, i.e., CASE type statements.